package leetcode.editor.cn.dsa18_searchtree;
// 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
//
// 二叉搜索树的定义如下： 
// 任意节点的左子树中的键值都 小于 此节点的键值。
// 任意节点的右子树中的键值都 大于 此节点的键值。 
// 任意节点的左子树和右子树都是二叉搜索树。 
//
// 示例 1： 
// 输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
// 输出：20
// 解释：键值为 3 的子树是和最大的二叉搜索树。
//
// 示例 2： 
// 输入：root = [4,3,null,1,2]
// 输出：2
// 解释：键值为 2 的单节点子树是和最大的二叉搜索树。
//
// 示例 3： 
// 输入：root = [-4,-2,-5]
// 输出：0
// 解释：所有节点键值都为负数，和最大的二叉搜索树为空。
//
// 示例 4： 
// 输入：root = [2,1,3]
// 输出：6
//
// 示例 5： 
// 输入：root = [5,4,8,3,null,6,3]
// 输出：7
//
// 提示： 
// 每棵树最多有 40000 个节点。
// 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。 
// 
// Related Topics 二叉搜索树 动态规划 
// 👍 40 👎 0


public class MaximumSumBstInBinaryTree1373 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int res = Integer.MIN_VALUE;
        public int maxSumBST(TreeNode root) {
            // 前序遍历每一个节点，判断是否是BST并得到最大键值和
            if (root == null) {
                // 空子树键值和为0，但是有可能res得到的和是负数，此时0更大
                res = res > 0 ? res : 0;
                return res;
            }
            int[] state = isValidBST(root); // 遍历根结点
            if(state[0]==1){
                res = res > state[2] ? res : state[2];// 更新目标值
            }
            maxSumBST(root.left);// 遍历左子树
            maxSumBST(root.right);// 遍历右子树
            return res;
        }
        // 判断一棵二叉树是BST，并返回键值和
        public int[] isValidBST(TreeNode root) {
            int[] state = new int[3]; // 使用一个数组来记录函数返回值和状态值
            state[0] = 1; // isBST 初始值为1
            state[1] = Integer.MIN_VALUE; // preNoeValue，初始值为整数最小值
            state[2]=0; // 键值和，初始值为0
            helper(root, state);
            return state;
        }
        private void helper(TreeNode root, int[] state) {
            if (root == null) return; // 空结点子树是BST，键值和为0
            helper(root.left, state); // 遍历左子树
            // 如果序列非递增 or 左子树不是BST
            if (root.val <= state[1] || state[0] == 0) {
                state[0] = 0;
                state[2] = 0;
                return; // 任意节点不满足条件说明该树就不是BST
            }
            state[1] = root.val; // 记录根结点值
            state[2] += root.val; // 将根结点值加入到键值和中
            helper(root.right, state); // 继续遍历右子树
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}